package LeetCode;

import java.nio.charset.CharsetEncoder;
import java.util.HashMap;
import java.util.Map;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:57
 */
public class interview0101 {
    //实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

    public static void main(String[] args) {
        System.out.println(new interview0101().isUnique2("hahha"));
    }
    public boolean isUnique(String astr) {
        if (astr == "" || astr == null){
            return  false;
        }
        char index = astr.charAt(0);
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < astr.length(); i++){
            map.put(astr.charAt(i),0);
        }
        for (int i = 0; i < astr.length(); i++){
            if (map.get(astr.charAt(i)) == 1) {
                return false;
            }else {
                map.put(astr.charAt(i), map.get(astr.charAt(i)) + 1);
            }
        }
        return true;
    }

    //空间复杂度为O（1）的解法 只要先进行排序就会有相同的字符在一起的情况
    //二空间复杂度只用考虑排序算法
    // 考虑到时间复杂度 堆排序就是最佳的选择
    // 先编写堆排序的代码 不使用递归实现
    public void heapify(char[] chas,int i,int size){
        int left = i * 2 + 1;//左子树
        int right = i * 2 +2;//右子树
        int largest = i;
        while (left < size){
            if (chas[left] > chas[i]){
                largest = left;
            }
            if (right < size && chas[right] > chas[largest]){
                largest = right;
            }
            if (largest != i){
                char tmp = chas[largest];
                chas[largest] = chas[i];
                chas[i] = tmp;
            }else {
                break;
            }
        }
    }

    public void heapInsert(char[] chas,int i){//去除大顶堆的最大值
        int parent = 0;
        while (i != 0){
            parent =  (i - 1) / 2;
            if (chas[parent] < chas[i]){
                char tmp = chas[parent];
                chas[parent] = chas[i];
                chas[i] = tmp;
                i = parent;
            }else {
                break;
            }
        }
    }

    public void heapSort(char[] chas){
        for (int i = 0; i < chas.length; i++){
            heapInsert(chas,i);
        }
        for (int i = chas.length - 1; i > 0; i--){
            char tmp = chas[0];
            chas[0] = chas[i];
            chas[i] = tmp;
            heapify(chas,0,i);
        }
    }

    public boolean isUnique2(String string){
        if (string == "" || string == null){
            return true;
        }
        heapSort(string.toCharArray());
        for (int i = 1; i < string.length(); i++){
            if (string.charAt(i) == string.charAt(i - 1)){
                return false;
            }
        }
        return true;
    }
}
